/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* next;

    Node() {}

    Node(int _val) {
        val = _val;
        next = NULL;
    }

    Node(int _val, Node* _next) {
        val = _val;
        next = _next;
    }
};
*/

class Solution
{
public:
    Node *insert(Node *head, int insertVal)
    {
        if (head == nullptr)
        {
            Node *node = new Node(insertVal);
            node->next = node;
            return node;
        }
        if (head->next == head)
        {
            head->next = new Node(insertVal, head);
            return head;
        }

        Node *node = head;
        while (true)
        {
            if ((insertVal >= node->val && insertVal <= node->next->val) || (node->val > node->next->val && (insertVal >= node->val || insertVal <= node->next->val)))
            {
                Node *insertNode = new Node(insertVal, node->next);
                node->next = insertNode;
                return head;
            }
            node = node->next;
            if (node == head)
            {
                Node *insertNode = new Node(insertVal, node->next);
                node->next = insertNode;
                return head;
            }
        }
        return head;
    }
};